|
Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it resembles long division of the binary message string, with a fixed number of zeroes appended, by the "generator polynomial" string except that exclusive OR operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register, and in software by a series of equivalent algorithms, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated) through byte-wise parallelism and space-time tradeoffs. Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final exclusive OR step and, most critically, a bit ordering (endianness). As a result, the code seen in practice deviates confusingly from "pure" division,〔 and the register may shift left or right. == Example == As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character "W", which is binary 010101112, decimal 8710, or hexadecimal 5716. For illustration, we will use the CRC-8-ATM (HEC) polynomial . Writing the first bit transmitted (the coefficient of the highest power of ) on the left, this corresponds to the 9-bit string "100000111". The byte value 5716 can be transmitted in two different orders, depending on the bit ordering convention used. Each one generates a different message polynomial . Msbit-first, this is = 01010111, while lsbit-first, it is = 11101010. These can then be multiplied by to produce two 16-bit message polynomials . Computing the remainder then consists of subtracting multiples of the generator polynomial . This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1, and the subtractions borrow "from infinity" instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it. |} Observe that after each subtraction, the bits are divided into three groups: at the beginning, a group which is all zero; at the end, a group which is unchanged from the original; and a blue shaded group in the middle which is "interesting". The "interesting" group is 8 bits long, matching the degree of the polynomial. Every step, the appropriate multiple of the polynomial is subtracted to make the zero group becomes one bit longer, and the unchanged group becomes one bit shorter, until only the final remainder is left. In the msbit-first example, the remainder polynomial is . Converting to a hexadecimal number using the convention that the highest power of ''x'' is the msbit; this is A216. In the lsbit-first, the remainder is . Converting to hexadecimal using the convention that the highest power of ''x'' is the lsbit, this is 1916. 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Computation of cyclic redundancy checks」の詳細全文を読む スポンサード リンク
|